#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include "dijkstra.h"


void relacher_init(int** liens,int** distances,int nb_terminaux,int i,int* d, int* pere){
  int n;
  for(n=0;n<nb_terminaux;n++){
    d[n]=-1;
    pere[n]=-1;
  }
  d[i]=0;
}

void relacher(int** liens,int** distances,int nb_terminaux,int u,int v,int* d, int* pere){
  if(d[u]!=-1&&(d[v]>(d[u]+distances[u][v])||d[v]==-1)){
    d[v]=(d[u]+distances[u][v]);
    pere[v]=u;
  }
}


int est_vide(int* t,int n){
  int i;
  for(i=0;i<n;i++)
    if(t[i]==1)
      return 0;
  return 1;
}

int accessible1(int* Y,int *d, int nb_terminaux){
  int i;
  for(i=0;i<nb_terminaux;i++)
    if(Y[i]==1&&d[i]!=-1)
      return 1;
  return 0;
}

int choix_u(int* Y,int* d,int nb_terminaux){
  int i;
  int min;
  int umin;

  if(accessible1(Y,d,nb_terminaux)==1){
      for(i=0;i<nb_terminaux;i++)
	if(Y[i]==1&&d[i]!=-1){
	  min=d[i];
	  umin=i;
	}
      for(i=0;i<nb_terminaux;i++)
	if(Y[i]==1&&d[i]!=-1&&d[i]<min){
	  umin=i;
	  min=d[i];
	}        
      return umin;
    }
    else
      for(i=0;i<nb_terminaux;i++)
	if(Y[i]==1)
	  return i;
	  
}

void dijkstra(int** liens,int** distances,int nb_terminaux,int s,int* d, int* pere){
  relacher_init(liens,distances,nb_terminaux,s,d,pere);
  int Y[nb_terminaux];
  int i;
  int u;
  int v;
  for(i=0;i<nb_terminaux;i++)
    Y[i]=1;
  while(est_vide(Y,nb_terminaux)==0){
    u=choix_u(Y,d,nb_terminaux);
    Y[u]=0;
    for(v=0;v<nb_terminaux;v++)
      if(liens[u][v]==1&&Y[v]==1)
	relacher(liens,distances,nb_terminaux,u,v,d,pere);
  }
}
